# -*- coding: UTF-8 -*-
from typing import List
from leetcode_helper import TestcaseHelper, SolutionBase


class Solution(SolutionBase):
    # 解题的方法，命名和Leetcode的保持一致即可
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # 得到每个状态对应的值，便于比较
        def get_state_value(state: List[List[int]]) -> int:
            value = 0

            for i in range(2):
                for j in range(3):
                    value = value * 10 + state[i][j]

            return value

        def swap(swap_state: List[List[int]], row0, col0, row1, col1):
            temp = swap_state[row1][col1]
            swap_state[row1][col1] = swap_state[row0][col0]
            swap_state[row0][col0] = temp

        # 将src_state[row][col]的元素移动4个方向
        # 0 - 上
        # 1 - 下
        # 2 - 左
        # 3 - 右
        def get_state(src_state: List[List[int]], row: int, col: int, direction: int) -> List:
            new_state = [src_state[i].copy() for i in range(len(src_state))]

            if direction == 0:
                if row > 0:
                    swap(new_state, row, col, row - 1, col)
            elif direction == 1:
                if row < len(src_state) - 1:
                    swap(new_state, row, col, row + 1, col)
            elif direction == 2:
                if col > 0:
                    swap(new_state, row, col, row, col - 1)
            elif direction == 3:
                if col < len(src_state[0]) - 1:
                    swap(new_state, row, col, row, col + 1)

            return new_state

        def get_children(parent_state: List[List[int]]) -> List:
            children = []
            row = 0
            col = 0

            for i in range(2):
                for j in range(3):
                    if parent_state[i][j] == 0:
                        row = i
                        col = j
                        break

            for direction in range(4):
                child = get_state(parent_state, row, col, direction)
                children.append(child)

            return children

        state_queue = [[board, 0]]
        visited_set = set()
        target_state = [[1, 2, 3], [4, 5, 0]]
        target_state_value = get_state_value(target_state)

        if get_state_value(board) == target_state_value:
            return 0

        ans_move_count = -1

        while len(state_queue) > 0:
            current_states = state_queue.copy()
            state_queue.clear()

            for state in current_states:
                children_states = get_children(state[0])

                for child_state in children_states:
                    child_state_value = get_state_value(child_state)
                    if child_state_value in visited_set:
                        continue

                    if get_state_value(child_state) == target_state_value:
                        ans_move_count = state[1] + 1
                        return ans_move_count

                    visited_set.add(child_state_value)
                    state_queue.append([child_state, state[1] + 1])

        return ans_move_count


if __name__ == '__main__':
    solution = Solution()

    # 按照leetcode的题目说明，将基本的test case填入
    # 每条case的最后一个元素是正确的结果，即期待的结果
    # 使用元组来保存输入的数据，期待的结果
    testcases = [
        ([[1, 2, 3], [4, 0, 5]], 1),
        ([[1, 2, 3], [5, 4, 0]], -1),
        ([[4, 1, 2], [5, 0, 3]], 5),
        ([[3, 2, 4], [1, 5, 0]], 14)
    ]

    for case_item in testcases:
        # 获取测试用的case和期待的执行结果
        input1 = case_item[0]
        expect = case_item[len(case_item) - 1]

        exec_result = solution.slidingPuzzle(input1)

        # 判断执行结果，输出提示信息
        check_result = solution.check_result(expect, exec_result)
        TestcaseHelper.print_case(check_result, case_item, exec_result)
